package my.sort;

import my.sort.cmp.SelectionSort;
import my.sort.cmp.ShellSort;

import java.text.DecimalFormat;

/**
 * 排序公共父类
 *
 * @author AJun
 * @date 2020/9/15
 */
public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {

    /**
     * 要排序的数组
     */
    protected T[] array;

    /**
     * 比较次数
     */
    protected int cmpCount;

    /**
     * 交换次数
     */
    protected int swapCount;

    /**
     * 排序执行时间
     */
    private long time;

    /**
     * 小数格式化
     */
    private final DecimalFormat fmt = new DecimalFormat("#.00");

    public void sort(T[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        this.array = array;

        long begin = System.currentTimeMillis();
        sort(); // 排序
        time = System.currentTimeMillis() - begin;
    }

    /**
     * 子类需要实现的排序算法
     */
    protected abstract void sort();

    /**
     * 比较数组中 i1 和 i2 索引处的元素的大小
     *
     * @param i1 第一个元素索引
     * @param i2 第二个元素索引
     * @return 0:array[i1]==array[i2]; 大于0:array[i1]>array[i2];  小于0:array[i1]<array[i2]
     */
    protected int cmp(int i1, int i2) {
        cmpCount++;
        return array[i1].compareTo(array[i2]);
    }

    /**
     * 比较数组中元素的大小
     *
     * @param v1 第一个元素
     * @param v2 第二个元素
     * @return 0:v1==v2; 大于0:v1>v2;  小于0:v1<v2
     */
    protected int cmp(T v1, T v2) {
        cmpCount++;
        return v1.compareTo(v2);
    }

    /**
     * 交换数组中 i1 和 i2 索引处的元素
     *
     * @param i1 第一个元素索引
     * @param i2 第二个元素索引
     */
    protected void swap(int i1, int i2) {
        swapCount++;
        T tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    @Override
    public int compareTo(Sort<T> o) {
        int result = (int) (time - o.time);
        if (result != 0) {
            return result;
        }

        result = cmpCount - o.cmpCount;
        if (result != 0) {
            return result;
        }

        return swapCount - o.swapCount;
    }

    @Override
    public String toString() {
        String timeStr = "耗时: " + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较: " + numberString(cmpCount);
        String swapCountStr = "交换: " + numberString(swapCount);
        // 最后再看稳定性，不能影响 cmpCount 和 swapCount
        String stableStr = "稳定性: " + isStable();
        return "[" + getClass().getSimpleName() + "]\n"
            + stableStr + " \t"
            + timeStr + " \t"
            + compareCountStr + "\t "
            + swapCountStr + "\n"
            + "------------------------------------------------------------------";
    }

    /**
     * 格式化数字
     */
    private String numberString(int number) {
        if (number < 10000) {
            return "" + number;
        }

        if (number < 100000000) {
            return fmt.format(number / 10000.0) + "万";
        }
        return fmt.format(number / 100000000.0) + "亿";
    }

    /**
     * 测评排序算法稳定性
     */
    @SuppressWarnings("unchecked")
    private boolean isStable() {
        if (this instanceof RadixSort || this instanceof CountingSort
            || this instanceof BucketSort) {
            return true;
        }
        if (this instanceof ShellSort || this instanceof SelectionSort) {
            return false;
        }

        Student[] students = new Student[20];
        for (int i = 0; i < students.length; i++) {
            students[i] = new Student(i * 10, 10);
        }
        sort((T[]) students);
        for (int i = 1; i < students.length; i++) {
            int score = students[i].score;
            int prevScore = students[i - 1].score;
            if (score != (prevScore + 10)) return false;
        }
        return true;
    }

    /**
     * 测试稳定性的类
     */
    private static class Student implements Comparable<Student> {
        public int score;
        public int age;

        public Student(int score, int age) {
            this.score = score;
            this.age = age;
        }

        @Override
        public int compareTo(Student o) {
            return age - o.age;
        }
    }

}
